package zw_201_300.zw_290_单词规律;

import java.util.HashMap;
import java.util.Map;

class Solution {

    /**
     * 哈希表
     * 思路及解法
     * 在本题中，我们需要判断字符与字符串之间是否恰好一一对应。
     * 即任意一个字符都对应着唯一的字符串，任意一个字符串也只被唯一的一个字符对应。在集合论中，这种关系被称为「双射」。
     * 想要解决本题，我们可以利用哈希表记录每一个字符对应的字符串，以及每一个字符串对应的字符。然后我们枚举每一对字符与字符串的配对过程，
     * 不断更新哈希表，如果发生了冲突，则说明给定的输入不满足双射关系。
     * 在实际代码中，我们枚举pattern 中的每一个字符，利用双指针来均摊线性地找到该字符在str 中对应的字符串。
     * 每次确定一个字符与字符串的组合，我们就检查是否出现冲突，最后我们再检查两字符串是否比较完毕即可。
     *
     * @param pattern
     * @param str
     * @return
     */
    public boolean wordPattern(String pattern, String str) {
        Map<String, Character> str2ch = new HashMap<String, Character>();
        Map<Character, String> ch2str = new HashMap<Character, String>();
        int m = str.length();
        int i = 0;
        for (int p = 0; p < pattern.length(); ++p) {
            char ch = pattern.charAt(p);
            if (i >= m) {
                return false;
            }
            int j = i;
            while (j < m && str.charAt(j) != ' ') {
                j++;
            }
            String tmp = str.substring(i, j);
            if (str2ch.containsKey(tmp) && str2ch.get(tmp) != ch) {
                return false;
            }
            if (ch2str.containsKey(ch) && !tmp.equals(ch2str.get(ch))) {
                return false;
            }
            str2ch.put(tmp, ch);
            ch2str.put(ch, tmp);
            i = j + 1;
        }
        return i >= m;
    }


//    public boolean wordPattern(String pattern, String str) {
//        String[] words = str.split(" ");
//        //字符和单词是互相映射，数量必须相等
//        if (words.length != pattern.length()) {
//            return false;
//        }
//        Map<Object, Integer> map = new HashMap<>();
//        for (Integer i = 0; i < words.length; i++) {
//            /*
//             调用put方法时，如果已经存在一个相同的key， 则返回的是前一个key对应的value，
//             同时该key的新value覆盖旧value，如果是新的一个key，则返回的是null。
//                如果key不存在，插入成功，返回null；如果key存在，返回之前对应的value。
//
//                以pattern = "abba", str = "dog cat cat dog"为例，
//                第1次：map.put('a',0)返回null，map.put("dog",0)返回null，两者相等；
//                第2次：map.put('b',1)返回null，map.put("cat",1)返回null，两者相等；
//                第3次：map.put('b',2)返回1，map.put("cat",2)返回1，两者相等；
//                第4次：map.put('a',3)返回0，map.put("dog",3)返回0，两者相等，
//                结果为 true。
//
//                以pattern = "abba", str = "dog cat cat fish"为例，
//                第1次：map.put('a',0)返回null，map.put("dog",0)返回null，两者相等；
//                第2次：map.put('b',1)返回null，map.put("cat",1)返回null，两者相等；
//                第3次：map.put('b',2)返回1，map.put("cat",2)返回1，两者相等；
//                第4次：map.put('a',3)返回0，map.put("fish",3)返回null，两者不相等，
//                结果为 false。
//            */
//            if (map.put(pattern.charAt(i), i) != map.put(words[i], i)) {
//                return false;
//            }
//        }
//        return true;
//    }
}
